#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pos, neg;
        int sum = 0;
        for(auto e: nums)
        {
            sum += e;
            if(e < 0) neg.push(e);
            else pos.push(e);
        }
        while(k)
        {
            if(neg.size())
            {
                k--;
                // 这里需要注意的细节是由于是模拟进行的
                // 把一个负数变成正数后也有可能是正数的最小值
                // 所以需要把他也放进正数的priority_queue中
                sum += -2 * neg.top();
                pos.push(-1 * neg.top());
                neg.pop();

            }
            else
                break;
        }
        // 到这里没有负数了，说明一定要扣去正数或者抵消
        if(k % 2 == 0) return sum;
        else return sum - 2 * pos.top();
    }
};